Basic information
I am Jiatu Li (李嘉图), a first-year graduate student at MIT theory group, advised by Prof. Ryan Williams. I obtained my Bachelor’s degree from ``Yao Class”, Institute for Interdisciplinary Information Science (IIIS), Tsinghua University.
My research interests are about circuit complexity, meta-complexity, and proof complexity. Recently, I am interested in the following concrete directions:
- The strength of Bounded Arithmetic, the fragments of Peano that capture the complexity of reasoning (see, e.g., Youtube Talk by Sam Buss). Can we prove strong lower bounds in Cook’s theory PV$_1$ or Buss’s theory $S^1_2$? Can we separate Jerabek’s theory APC$_1$ and Cook’s PV$_1$? Can we identify the relative strengths of combinatorial principles and theorems as a feasible analogy of the program of Reverse Mathematics? Our partial results: APC vs PV, reverse mathematics, unprovability, unprovability’
- The complexity of the Range Avoidance Problem (see Kor21, RSW22). What is the computational complexity of finding a non-output of an $n$-input $(n+1)$-output circuit? What if the circuit is a restricted one, say, an AC$_0$ circuit? Our partial results: upper bound, lower bound 1, lower bound 2
- Proving unconditional complexity lower bounds (e.g. MW18, Chen23, CHR23, Li23) and derandomization results (e.g. CLORS23). Our partial results: catalytic, general, PRFs
As complexity theorists, our mission is to liberate the warriors trying to solve inherently hard problems. Sometimes we can use their stories to alleviate insomnia for cryptographers (see, e.g., Cryptographers Seldom Sleep Well).
I am also interested in writing formal (i.e. computer verified) mathematical proofs in Coq and Lean. Although it seems to be incredible nowadays, I believe that proof assistants will eventually be able to help mathematicians in their research (if mathematicians are not completely replaced by something like GPT-256, see, e.g., ChatGPT).
Experience
- PhD Student: MIT (2023-)
- Undergraduate Student: Tsinghua University (2019-2023)
- Undergraduate Research Intern: University of Warwick (2022.3-2022.7), Advised by Dr. Igor Carboni Oliveira
- Undergraduate Research Intern: Shanghai Qi Zhi Institute (2022.8-2022.9), Advised by Dr. Yilei Chen
Publication
In theoretical computer science, the authors are usually listed in alphabetical order.
See publication for summaries.
Conference Papers
- Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness. FOCS 2024 (to appear). Jiatu Li, Edward Pyne, Roei Tell.
- Reverse Mathematics of Complexity Lower Bounds. FOCS 2024 (to appear). Lijie Chen, Jiatu Li, Igor C. Oliveira.
- Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography. STOC 2024. Yilei Chen and Jiatu Li.
- Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic. STOC 2023. Rahul Ilango, Jiatu Li, R. Ryan Williams.
- Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms. STOC 2023. Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren.
- Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic. STOC 2023. Jiatu Li, Igor C. Oliveira.
- Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs. CCC 2022. Lijie Chen, Jiatu Li, Tianqi Yang.
- The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity. STOC 2022 (Best Student Paper). Zhiyuan Fan, Jiatu Li, Tianqi Yang.
- $3.1n−o(n)$ Circuit Lower Bounds for Explicit Functions. STOC 2022. Jiatu Li, Tianqi Yang.
Manuscripts
- The Structure of Catalytic Space: Capturing Randomness and Time via Compression. 2024. James Cook, Jiatu Li, Ian Mertz, Edward Pyne.
- On the Unprovability of Circuit Size Bounds in Intuitionistic $S^1_2$. 2024. Lijie Chen, Jiatu Li, Igor C. Oliveira.
How to contact me?
- Email 1: jiatuli AT mit DOT edu
- Email 2: ljt714285 AT gmail DOT com
- Github: http://github.com/ljt12138/
If you have any questions or comments about my papers, essays, and any other projects, please feel free to contact me. I will be more than happy to hear from anyone interested in my work.
Interesting facts about me
- My name, Li Jiatu, is the same as the Chinese translation of Ricardo. My parents chose the name when they were reading The Capital of Karl Marx, in which the name David Ricardo occurs constantly.
- I learned Go (the chess game, not the programming language) when I was a kid and achieved amateur four-dan. Inspired by recent Livestreams of professional Go players in China, I’m now interested in playing go again. My ID on Fox Weiqi is jiatu1li (6d). I am a member of the MIT Go Club and you could probably catch me in the meetings (check https://www.meetup.com/massgo/ for the schedule).